//现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequ
//isites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。 
//
// 
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 
// 
//
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：[0,1]
//解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
// 
//
// 示例 2： 
//
// 
//输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出：[0,2,1,3]
//解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
//因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。 
//
// 示例 3： 
//
// 
//输入：numCourses = 1, prerequisites = []
//输出：[0]
// 
//
// 
//提示：
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= numCourses * (numCourses - 1) 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// ai != bi 
// 所有[ai, bi] 匹配 互不相同 
// 
//
// 
//
// 拓展： 
//
// 
// 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。 
// 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。 
// 
// 拓扑排序也可以通过 BFS 完成。 
// 
// 
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 
// 👍 505 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CourseScheduleIi {
    public static void main(String[] args) {
        int[][] nums = {{1,0}};
        new CourseScheduleIi().new Solution().findOrder(2, nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 拓扑排序，使用bfs方式进行的拓扑排序，遍历的过程中将元素添加到课程即可
         * 使用了一个index来记录返回结果下标，遍历结束后如果index==numCourses说明所有元素都遍历到，不存在环路，返回结果集
         * 如果并不是所有元素都可以遍历到，那么返回空结果集
         *
         * bfs遍历图的时候，需要一个节点入度表，一个邻接表
         * 思路非常的直接：
         *      首先遍历所有的prerequisites，统计各个节点的入度以及添加元素的所有后继节点
         *      之后遍历所有入度节点为0的元素，先将其添加到结果集中去，然后将其所有后继节点的入度--
         *      将入度为0的所有后继节点加入到queue进行遍历，如果没有环路的话，所有的节点都可以访问到
         */
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] indegrees = new int[numCourses];//节点入度表
            int[] res = new int[numCourses];
            Queue<Integer> queue = new LinkedList<>();
            List<List<Integer>> lists = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) lists.add(new ArrayList<>());
            for (int[] prerequisite : prerequisites){
                indegrees[prerequisite[0]]++;
                lists.get(prerequisite[1]).add(prerequisite[0]);
            }
            //寻找入度为0的课程
            for (int i = 0; i < numCourses ; i++) if (indegrees[i] == 0) queue.offer(i);
            int index = 0;//这是为了储存元素设置的下标
            while (!queue.isEmpty()){
                Integer pre = queue.poll();
                res[index++] = pre;
                for (int cur : lists.get(pre) )
                    // 入度为0之后加入队列，不为0的话说明还有前导课程要学
                    if (--indegrees[cur] == 0) queue.offer(cur);
            }
            if (index == numCourses) return res;
            else return new int[0];
        }

        /**
         * 可能是二刷，也可能是三刷，一开始使用dfs没写出来
         * 使用bfs解决时思路较为直接：使用入度表，入度为0时加入queue中
         */
        public int[] findOrder2(int numCourses, int[][] prerequisites) {
            int[] indegrees = new int[numCourses];
            int[] res = new int[numCourses];
            List<List<Integer>> matrix = new ArrayList<>();
            for (int i = 0; i < numCourses; i++)
                matrix.add(new ArrayList<>());
            for (int[] prerequisite : prerequisites){
                indegrees[prerequisite[0]]++;
                matrix.get(prerequisite[1]).add(prerequisite[0]);
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < numCourses; i++) if (indegrees[i] == 0) queue.add(i);
            int index = 0;// 表示下标，同时记录课程数
            while (!queue.isEmpty()){
                int pre = queue.poll();
                res[index++] = pre;
                for (int c : matrix.get(pre)){
                    if (--indegrees[c] == 0) queue.add(c);
                }
            }
            if (index == numCourses) return res;
            else return new int[0];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}






























